package q188_maxProfit;

import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.maxProfit(2, new int[]{1,2,3,4}));

    }

    /**
     * 与123题类似，但是需要建立数组进行计算
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit(int k, int[] prices) {
        if (k == 0 || prices.length <= 1){
            return 0;
        }
        // 首先是建立buys和sells的数组，但是需要考虑的是，如果要在遍历的过程中直接循环得到每一个buy和sell
        // 那么buys0 和 sells0 如何设置
        int[] buys = new int[k + 1];
        int[] sells = new int[k + 1];
        // 首先将所有buys都设置为第一天的股价
        Arrays.fill(buys, prices[0]);
        // 注意，这里实际上用i = 0开始也没有问题，但是从实际的买卖上来看，设置为1开始比较合理，并且能减少计算
        for (int i = 1; i < prices.length; i++) {
            // 循环的计算每一个buys和sells，但是需要注意的是这里j = 1开始
            // 这意味着 buys0 和 sells0 不会被再次更新，buys0本就不在买卖中所以不考虑
            // （1 - k 才是我们关注的 k 次买卖，buys0实际上不存在）
            // 我们从123题上来看，实际上，只在buys2的时候需要有一个price[i] - sells1
            // 那么我们只需要在每一个buys[j]有一个prices[i] - sells[j - 1]
            // 但是一开始buys1的时候没有sells0， 只有price 所以我们要让sells0一直是0，所以才会有k + 1的数组
            for (int j = 1; j <= k; j++) {
                buys[j] = Math.min(buys[j], prices[i] - sells[j - 1]);
                sells[j] = Math.max(sells[j], prices[i] - buys[j]);
            }
        }

        return sells[k];
    }
}
